翻訳と辞書
Words near each other
・ Methodius Stratiev
・ Methodius Terleckyj
・ Methodological advisor
・ Methodological individualism
・ Methodological solipsism
・ Methodology
・ Methodology of econometrics
・ Methodrone
・ Methods (journal)
・ Methods engineering
・ Methods for Attaining Extreme Altitudes
・ Methods in Ecology and Evolution
・ Methods in Enzymology
・ Methods in Molecular Biology
・ Methods of coin debasement
Methods of computing square roots
・ Methods of contour integration
・ Methods of detecting exoplanets
・ Methods of divination
・ Methods of Execution
・ Methods of Information in Medicine
・ Methods of Mayhem
・ Methods of Mayhem (album)
・ Methods of neuro-linguistic programming
・ Methods of obtaining knowledge
・ Methods of passing as female
・ Methods of passing as male
・ Methods of payment in International trade
・ Methods of pluton emplacement
・ Methods of praying the rosary


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Methods of computing square roots : ウィキペディア英語版
Methods of computing square roots

In numerical analysis, a branch of mathematics, there are several square root algorithms or methods of computing the principal square root of a nonnegative real number. For the square roots of a negative or complex number, see below.
Finding \sqrt is the same as solving the equation f(x) = x^2 - S = 0\,\!. Therefore, any general numerical root-finding algorithm can be used. Newton's method, for example, reduces in this case to the so-called Babylonian method:
:x_=x_n-\frac=x_n-\frac=\frac\left(x_n+\frac\right)
Generally, these methods yield approximate results. To get a higher precision for the root, a higher precision for the square is required and a larger number of steps must be calculated.
== Rough estimation ==
Many square root algorithms require an initial seed value. If the initial seed value is far away from the actual square root, the algorithm will be slowed down. It is therefore useful to have a rough estimate, which may be very inaccurate but easy to calculate. With S expressed in scientific notation as a\times10^ where 1\leq a<100 and ''n'' is an integer, the square root \sqrt = \sqrt\times10^n can be estimated as
: \sqrt \approx \begin
2 \cdot 10^n & \text a < 10, \\
6 \cdot 10^n & \text a \geq 10.
\end
The factors two and six are used because they approximate the geometric means of the lowest and highest possible values with the given number of digits: \sqrt} = \sqrt() \approx 2 \, and \sqrt} = \sqrt() \approx 6 \,.
For S = 125348 = 12.5348 \times 10^4, the estimate is \sqrt \approx 6 \cdot 10^2 = 600.
When working in the binary numeral system (as computers do internally), by expressing S as a\times2^ where 0.1_2\leq a<10_2, the square root \sqrt = \sqrt\times2^n can be estimated as \sqrt \approx 2^n, since the geometric mean of the lowest and highest possible values is \sqrt} = \sqrt() = 1.
For S = 125348 = 1\;1110\;1001\;1010\;0100_2 = 1.1110\;1001\;1010\;0100_2\times2^\, the binary approximation gives \sqrt \approx 2^8 = 1\;0000\;0000_2 = 256\, .
These approximations are useful to find better seeds for iterative algorithms, which results in faster convergence.
== Babylonian method ==
Perhaps the first algorithm used for approximating is known as the Babylonian method, named after the Babylonians,〔There is no direct evidence showing how the Babylonians computed square roots, although there are informed conjectures. (Square root of 2#Notes gives a summary and references.)〕 or "Hero's method", named after the first-century Greek mathematician Hero of Alexandria who gave the first explicit description of the method. It can be derived from (but predates by 16 centuries) Newton's method. The basic idea is that if is an overestimate to the square root of a non-negative real number then will be an underestimate and so the average of these two numbers may reasonably be expected to provide a better approximation (though the formal proof of that assertion depends on the inequality of arithmetic and geometric means that shows this average is always an overestimate of the square root, as noted in the article on square roots, thus assuring convergence).
More precisely, if is our initial guess of and is the error in our estimate such that , then we can expand the binomial and solve for
:e=\frac \approx \frac, since e \ll x .
Therefore, we can compensate for the error and update our old estimate as
:x := x + e = \frac = \frac}
Since the computed error was not exact, this becomes our next best guess. The process of updating is iterated until desired accuracy is obtained. This is a quadratically convergent algorithm, which means that the number of correct digits of the approximation roughly doubles with each iteration. It proceeds as follows:
#Begin with an arbitrary positive starting value (the closer to the actual square root of , the better).
#Let be the average of and (using the arithmetic mean to approximate the geometric mean).
#Repeat step 2 until the desired accuracy is achieved.
It can also be represented as:
:x_0 \approx \sqrt,
:x_ = \frac \left(x_n + \frac\right),
:\sqrt S = \lim_ x_n.
This algorithm works equally well in the s, but cannot be used to identify real square roots with -adic square roots; one can, for example, construct a sequence of rational numbers by this method that converges to +3 in the reals, but to −3 in the 2-adics.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Methods of computing square roots」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.